
package com.javazyw.utils.net;

import java.util.ArrayList;
import java.util.List;

/**
 * <p> 笛卡尔积工具类.</p>
 * 
 * @version v1.0
 * @author dongdh 
 * @date 2014-7-23
 * 
 */
public final class DescartesUtils {

    public static List<List<String>> cross(List<List<String>> crossArgs) {

        // 计算出笛卡尔积行数
        int rows = crossArgs.size() > 0 ? 1 : 0;

        for (List<String> data : crossArgs) {
            rows *= data.size();
        }

        // 笛卡尔积索引记录
        int[] record = new int[crossArgs.size()];

        List<List<String>> results = new ArrayList<List<String>>();

        // 产生笛卡尔积
        for (int i = 0; i < rows; i++) {
            List<String> row = new ArrayList<String>();

            // 生成笛卡尔积的每组数据
            for (int index = 0; index < record.length; index++) {
                row.add(crossArgs.get(index).get(record[index]));
            }

            results.add(row);
            crossRecord(crossArgs, record, crossArgs.size() - 1);
        }

        return results;
    }

    private static void crossRecord(List<List<String>> sourceArgs,
            int[] record, int level) {
        record[level] = record[level] + 1;

        if (record[level] >= sourceArgs.get(level).size() && level > 0) {
            record[level] = 0;
            crossRecord(sourceArgs, record, level - 1);
        }
    }

    public static void main(String[] args) {
        ArrayList l1 = new ArrayList();
        l1.add("1");
        l1.add("2");
        l1.add("3");
        ArrayList l2 = new ArrayList();
        l2.add("a");
        l2.add("b");

        ArrayList l3 = new ArrayList();
        l3.add("+");
        // l3.add("-");

        ArrayList ls = new ArrayList();
        ls.add(l1);
        ls.add(l2);
        ls.add(l3);

        List<List<String>> result = cross(ls);

        System.out.println(result);
        
        String s = "110000";
        System.out.println(s.substring(2));
    }

}
